The present invention is directed to the field of network communications. More specifically, this invention is directed to a method for assigning link weights that allows a network to function effectively during a single-link failure without changing link weights.
The main function of a communications network is to transfer information from a source to a remote destination. Generally, a communications network includes a number of nodes (usually devices called routers) coupled together by a number of links. Typically there are a number of paths, or routes, made up of nodes and links for information to travel from a particular source to a particular destination. The process of determining the specific nodes and links to utilize so that the information will reach its destination in an efficient manner is called “routing” and is preformed by a routing protocol.
Proper routing decisions are critical to realizing optimal network performance. There are two main goals when making routing decisions: keeping end-to-end delays low and ensuring that no link is overloaded. Low end-to-end delays can be achieved by choosing short traffic routes so as to minimize propagation delays. Similarly, link overloading can be averted by minimizing the maximum link load thereby balancing the traffic load evenly across the network.
In general, a routing protocol operates by reading portions of a packet to determine the packet's destination and then passes that information to a routing algorithm that determines the best route for the packet. More specifically, after receiving a packet, a router will read the packet's header to determine the source, the destination and any pertinent metrics associated with the packet, and then send that information to a routing algorithm. The routing algorithm uses the information received, together with information obtained from one or more routing tables, to calculate the best path to send the packet to its intended target.
There are several types of information stored in routing tables. One type of information is addressing information that allows a routing protocol to identify and locate the destination for a packet. For example, a routing table may contain a list of addresses for every device in the network environment. Alternatively, a routing table may contain a list of the devices that are physically connected to the router along with those destinations that may be reached from those devices.
A second type of information that may be stored in a routing table relates to the environmental factors that may affect the transfer of data over a particular link. Generally, this information is reduced to a number that is referred to as a link weight. Although a link weight may represent any meaningful factor, it is generally indicative of the relative value of using one path over another to a specific destination. Depending on the configuration of a network, a particular link weight may represent the amount of bandwidth available on the link, the link's reliability, the traffic flow over the link, or the amount of money charged by the company that owns the link.
As stated above, a typical routing algorithm will perform a calculation to determine the best path to a particular destination. When Intra-domain routing relies on IGP link state protocols, such as IS-IS or OSPF, the traffic is routed between any two nodes along the minimum cost path measured as the sum of the weights of all links along the path. If multiple paths exist with the same minimum cost, the traffic demand is split equally among these paths.
Several methods are used to assign link weights. One common method involves setting the weight of the link inverse to its capacity so that a link with a high capacity will attract more traffic and a link with a low capacity will attract less traffic. Another method involves assigning link weights proportional to the physical length of the link in order to minimize propagation delays. Yet another method involves observing the flow of traffic through the network and repeatedly adjusting the link weights to accommodate the traffic.
A major drawback of the current approaches, generally, is that they view link weight assignment as a static problem and therefore largely ignore network dynamics. Specifically, one of the main challenges for a network operator is dealing with transient link failures. For example, when a link fails, IS-IS/OSPF protocols divert traffic from the failed link to alternate paths without computing new link weights. This action has the potential to overload one or more links, which could lead to even more failures absent some action by the network operator.
The most obvious way to restore network performance after a link failure is to implement a network-wide reassignment of link weights. Indeed, studies have shown that changing just a few link weights is usually sufficient to balance the traffic after a link failure. There are, however, problems with this approach. First, in order to be utilized, the new link weight assignments must be sent to every router in the network, and the routers must then recompute their minimum cost path to every other router. These actions may take a significant amount of time during which the network is subject to considerable instability. Second, it has been observed that most link failures are relatively short-lived. These short transient failures often leave operators and/or routers with insufficient time to evaluate and then reassign link weights. Also, if the link weights are reassigned, the operators and/or routers often must implement a second reassignment a short time later when the link is restored. Thus, in the event of a link failure, operators have the choice of simply suffering the instability while hoping that the link failure is resolved quickly or attempting to recompute and then reassign link weights. The problem with the first choice, obviously, is that the failure may not be resolved quickly. The problem with the second choice is that it requires significant work in a short amount of time which may need to be performed a second time only moments later.
Thus, it is desirable to provide a method for determining a set of link weights that balances traffic loads and keeps end-to-end delay low both in the absence of failures and in the case of a link failure. Implementing a set of link weights as determined by the present invention will allow a network to function well when there is a link failure without changing the link weight assignments. Additional advantages and novel features of the invention will be set forth in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following, or may be learned from practice of the invention.